package com.example.canaldemospringboot.canal;

import com.example.canaldemospringboot.model.ListNode;
import com.example.canaldemospringboot.model.Parts;
import org.springframework.stereotype.Component;
import top.javatool.canal.client.annotation.CanalTable;
import top.javatool.canal.client.handler.EntryHandler;

import java.util.*;

/**
 * @Description:
 * @Author: dengping.xu
 * @Data: 2021-11-08
 */
@Component
@CanalTable(value = "tb_stockparts")
public class PartsCanalListener implements EntryHandler<Parts> {
    @Override
    public void insert(Parts parts) {
        System.out.println(parts);
    }

    @Override
    public void update(Parts before, Parts after) {
        System.out.println(before);
        System.out.println("============");
        System.out.println(after);
    }

    @Override
    public void delete(Parts parts) {
        System.out.println(parts);
    }

    public static void main(String[] args) {
        /*String haystack = "mississippi";
        String needle = "issip";
        System.out.println(strStr(haystack, needle));*/
//        System.out.println(grayCode(3));
//        System.out.println(0^1);
//        System.out.println(1^3);
//        System.out.println(3^2);
//        System.out.println(2^6);
//        System.out.println(6^7);
//        System.out.println(7^5);
//        System.out.println(5^4);
        //G(i) = i ^ (i/2);
//        System.out.println(2 ^ (2 / 2));
        /*String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";

        kmp(str1, str2);*/

        /*int[] nums = {1,2,3,4,5,6,7};
        rotate(nums,3);
        System.out.println(Arrays.toString(nums));*/
//        reserve(nums,0,7);
//        System.out.println(Arrays.toString(nums));
//        int[] res = {12,23,36,46,62};
//
//        System.out.println(slowestKey(res, "spuda"));

//        int[] nums = {0,1,0,3,12};
//        moveZeroes(nums);
//        System.out.println(Arrays.toString(nums));

        /*int[] nums = {0,1,0,3,12};
        int[] sum = twoSum(nums, 4);
        System.out.println(Arrays.toString(sum));*/
        /*String s = "Let's take LeetCode contest";
        System.out.println(reverseWords(s));*/
//        System.out.println(combine(4,2));
//        System.out.println(combinationSum3(9, 45));
//        System.out.println(letterCombinations(""));
//        System.out.println(checkInclusion("ab", "eidbaooo"));
//        int[] nums = {1,2,3};
//        System.out.println(permute(nums));
        /*int[][] image = {{1,1,1}, {1,1,0},{1,0,1}};
        System.out.println(Arrays.deepToString(floodFill(image, 1, 1, 2)));*/
        /*int[] nums = {2,3,6,7};
        System.out.println(combinationSum(nums, 7));*/
//        System.out.println(kSmallestPairs(new int[]{1, 2}, new int[]{3}, 3));


//        mergeTrees()
/*        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3)));
        reverseList(head);
        System.out.println(head);*/
        /*int[] nums = {10,1,2,7,6,1,5};
        System.out.println(combinationSum(nums,8));*/
//        int[] nums = {1,1,1,1,1,1,1,1};
        /*int i = removeDuplicates(nums);
        System.out.println(Arrays.toString(nums) + " i: " + i);*/
/*        int i = removeElement(nums, 2);
        System.out.println(Arrays.toString(nums) + " i: " + i);*/

//        System.out.println(Arrays.toString(searchRange(nums, 6)));

//        System.out.println(minSubArrayLen(11, nums));
//        System.out.println(fourSum(new int[]{1,-2,-5,-4,-3,3,3,5}, -11));
//        reverseStr("abcdefg", 8);
//        System.out.println(reverseWords("the sky is blue"));
//        System.out.println(evalRPN(new String[]{"10","6","9","3","+","-11","*","/","*","17","+","5","+"}));
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1}, 1)));
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length < 0){
            return null;
        }

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> rightPriorityQueue = new PriorityQueue<>(Comparator.reverseOrder());
        int fast = 0;
        int slow = 0;
        int rightFast = nums.length - 1;
        int rightSlow = nums.length - 1;
        int[] ret = new int[nums.length - k + 1];
        int i = 0;
        int j = ret.length - 1;
        while (fast <= rightSlow) {
            if(fast < k){
                priorityQueue.add(nums[fast++]);
            }else {
                ret[i++] = priorityQueue.peek();
                priorityQueue.add(nums[fast++]);
                priorityQueue.remove(nums[slow++]);
            }
            if(rightFast > nums.length - k - 1 ){
                rightPriorityQueue.add(nums[rightFast--]);
            }else {
                ret[j--] = rightPriorityQueue.peek();
                rightPriorityQueue.add(nums[rightFast--]);
                rightPriorityQueue.remove(nums[rightSlow--]);
            }
        }
        ret[i] = priorityQueue.peek();
        return ret;
    }



    public static int evalRPN(String[] tokens) {
        Deque<String> deque = new ArrayDeque<>();
        for (String token : tokens) {
            if("+".equals(token)  || "-".equals(token) || "/".equals(token) || "*".equals(token)){
                int num1 = Integer.parseInt(deque.pop());
                int num2 = Integer.parseInt(deque.pop());
                switch (token){
                    case "+":
                        deque.push(num2 + num1 + "");
                        break;
                    case "-":
                        deque.push(num2 - num1 + "");
                        break;
                    case "*":
                        deque.push(num2 * num1 + "");
                        break;
                    case "/":
                        deque.push(num2 / num1 + "");
                        break;
                }
            }else {
                deque.push(token);
            }
        }
        return Integer.parseInt(deque.peek());
    }

    public static String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == ' ') continue;
            StringBuilder subSb = new StringBuilder();
            while (i < s.length() &&s.charAt(i) != ' ') {
                subSb.append(s.charAt(i));
                i++;
            }
            sb.insert(0, subSb);
            sb.insert(0, " ");
        }
        return sb.charAt(0) == ' ' ? sb.deleteCharAt(0).toString() :sb.toString();
    }

    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            sb.append(c == ' ' ? "%20" : c);
        }
        return sb.toString();
    }


    public static String reverseStr(String s, int k) {
        char[] array = s.toCharArray();
        int left = 0, right = k - 1;
        if(right>=array.length){
            right = array.length - 1;
        }
        while (right < array.length){
            swap(array, left, right);
            left += 2 * k;
            right += 2 * k;
            if(left>= array.length){
                break;
            }
            if(right>=array.length){
                right = array.length - 1;
            }
        }
        return new String(array);
    }

    private static void swap(char[] array, int left, int right){
        while (left < right){
            char chars = array[left];
            array[left] = array[right];
            array[right] = chars;
            left++;
            right--;
        }
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            for (int j = nums.length - 1; j > i ; j--) {

                if (j < nums.length-1 && nums[j] == nums[j + 1]) {
                    continue;
                }

                int left = i + 1;
                int right = j - 1;
                while (right > left) {
                    int sum = nums[i] + nums[left] + nums[right] + nums[j];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[left], nums[right], nums[j]));

                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }

    public static int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        int count = Integer.MAX_VALUE;
        for (int left=0,right = 0; sum >= target || right < nums.length; ) {
            if(sum >= target){
                if(count > right - left ){
                    count = right - left;
                }
                sum = sum - nums[left++];
            }else {
                sum = sum + nums[right++];
            }
        }
        return count == Integer.MAX_VALUE ? 0 : count;
    }

    public static int[] searchRange(int[] nums, int target) {
        int high = nums.length - 1, low = 0;
        int mid = (low + high) / 2;
        int i = -1, j = -1;
        while (low < high) {
            if (nums[mid] < target) {
                low = mid + 1;
            } else if (nums[mid] > target) {
                high = mid - 1;
            } else {
                i = mid;
                j = mid;
                while (i >= 0 && nums[i] == target ){
                    i--;
                }
                while (j <= nums.length && nums[j] == target ){
                    j++;
                }
                i++;
                j--;
                break;
            }
            mid = (low + high) / 2;
        }
        return new int[]{i,j};
    }

    public void rotate(int[][] matrix) {

    }

    public static int removeDuplicates(int[] nums) {
        if(nums.length < 2)return nums.length;
        int i = 0;
        for (int cur = 1; cur < nums.length ; cur++) {
            if(nums[i] != nums[cur]){
                nums[++i] = nums[cur];
            }
        }
        return ++i;
    }

    public static int removeElement(int[] nums, int val) {
        if(nums.length < 1)return 0;
        int i = 0;
        for (int cur = 0; cur < nums.length ; cur++) {
            if(nums[cur] != val){
                nums[i++] = nums[cur];
            }
        }
        return i;
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> resultList  = new ArrayList<>();
        Arrays.sort(candidates);
        backtracking(resultList,new ArrayList<>(), candidates, target, 0, 0);
        return resultList;
    }

    private static void backtracking(List<List<Integer>> resultList, List<Integer> list, int[] candidates, int target, int sum,int index) {
        if(sum == target){
            for (List<Integer> item : resultList) {
                if(item.containsAll(list)&& item.size() == list.size()){
                    return;
                }
            }
            resultList.add(new ArrayList<>(list));
            return ;
        }
        for (int i = index; i < candidates.length; i++) {
            if(sum + candidates[i] > target)break;
            list.add(candidates[i]);
            backtracking(resultList,list,candidates,target,sum + candidates[i], i + 1);
            list.remove(list.size() - 1);
        }
    }

    /*private static void backtracking(List<List<Integer>> resultList, List<Integer> list,int[] nums, int index, int sum) {
        if(list.size() == 3){
            if(sum == 0){
                for (List<Integer> item : resultList) {
                    if(item.containsAll(list)){
                        return;
                    }
                }
                resultList.add(new ArrayList<>(list));
            }
            return;
        }
        for (int i = index; i < nums.length; i++) {
            list.add(nums[i]);
            backtracking(resultList, list, nums, i + 1, sum + nums[i]);
            list.remove(list.size() - 1);
        }
    }
*/
    public static ListNode reverseList(ListNode head) {
        if(head == null) return null;
        ListNode pre = null;
        ListNode next = head.next;
        while(next != null){
            head.next = pre;
            pre = head;
            head = next;
            next = next.next;
        }
        head.next = pre;
        return head;
    }

    public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        TreeNode node = new TreeNode(root1.val + root2.val);
        node.left = mergeTrees(root1.left, root2.left);
        node.right = mergeTrees(root1.right, root2.right);
        return node;
    }

    public static void merge(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            root1 = root2;
            return;
        }
        if (root2 == null) {
            return;
        }
        root1.val = root1.val + root2.val;
        merge(root1.left, root2.left);
        merge(root1.right, root2.right);
    }

    public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> resultList = new ArrayList<>();
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(k, (a, b) -> {
            return nums1[a[0]] + nums2[a[1]] - nums1[b[0]] - nums2[b[1]];
        });

        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            priorityQueue.offer(new int[]{i, 0});
        }
        while (k-- > 0 && !priorityQueue.isEmpty()) {
            int[] poll = priorityQueue.poll();
            resultList.add(Arrays.asList(nums1[poll[0]], nums2[poll[1]]));
            if (++poll[1] < nums2.length) {
                priorityQueue.offer(poll);
            }
        }
        return resultList;
    }


    /*public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> resultList = new ArrayList<>();
        backTracking(resultList, new ArrayList<>(), candidates, target, 0, 0);
        return resultList;
    }

    private static void backTracking(List<List<Integer>> resultList, List<Integer> list, int[] candidates, int target, int index, int sum) {
        if (target <= sum) {
            if (target == sum) {
                resultList.add(new ArrayList<>(list));
            }
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            list.add(candidates[i]);
            backTracking(resultList, list, candidates, target, index, sum + candidates[i]);
            list.remove(list.size() - 1);
        }
    }*/

    private void maxArea(int[][] grid, int i, int j, int count, List<Integer> list, int oldNum) {
        if (i >= grid.length || j >= grid[0].length) {
            return;
        }
        if (grid[i][j] == 0 && oldNum == 1) {
            return;
        }
        if (grid[i][j] == 1) {
            count++;
        }
        oldNum = grid[i][j];
        maxArea(grid, i + 1, j, count, list, oldNum);
        maxArea(grid, i, j + 1, count, list, oldNum);
    }

    public static int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int oldColor = image[sr][sc];
        fill(image, sr, sc, newColor, oldColor);
        return image;
    }

    private static void fill(int[][] image, int sr, int sc, int newColor, int oldColor) {
        if (sr >= image.length || sr < 0 || sc >= image[0].length || sc < 0 || image[sr][sc] == newColor || image[sr][sc] != oldColor) {
            return;
        }
        if (image[sr][sc] == oldColor) {
            image[sr][sc] = newColor;
        }
        fill(image, sr - 1, sc, newColor, oldColor);
        fill(image, sr + 1, sc, newColor, oldColor);
        fill(image, sr, sc - 1, newColor, oldColor);
        fill(image, sr, sc + 1, newColor, oldColor);
    }

    /*public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        boolean[] isUsed = new boolean[nums.length];
        backTracking(resultList, list, nums,isUsed);
        return resultList;
    }

    private static void backTracking(List<List<Integer>> resultList, List<Integer> list, int[] nums, boolean[] isUsed) {
        if(list.size() == nums.length){
            resultList.add(new ArrayList<>(list));
            return;
        }
        for (int j = 0; j < nums.length; j++) {
            if(!isUsed[j]){
                list.add(nums[j]);
                isUsed[j] = true;
            }
            backTracking(resultList, list, nums,isUsed);
            list.remove(list.size()-1);
        }
    }
*/

    public static boolean checkInclusion(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[] array = new int[26];
        for (int i = 0; i < m; i++) {
            --array[s1.charAt(i) - 'a'];
        }
        for (int left = 0, right = 0; right < n; right++) {
            int x = s2.charAt(right) - 'a';
            ++array[x];
            while (array[x] > 0) {
                --array[s2.charAt(left) - 'a'];
                left++;
            }
            if (right - left + 1 == m) {
                return true;
            }
        }
        return false;
    }
   /* public int lengthOfLongestSubstring(String s) {
    }*/

    public static int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        int up = 1;
        int down = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            }
            if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }

    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = s.length - 1, j = g.length - 1, num = 0;
        while (i >= 0 && j >= 0) {
            if (s[i] >= g[j]) {
                num++;
                i--;
                j--;
            } else {
                j--;
            }
        }
        return num;
    }

    public boolean increasingTriplet(int[] nums) {
        int a = Integer.MAX_VALUE;
        int b = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= a) {
                a = nums[i];
            } else if (nums[i] <= b) {
                b = nums[i];
            } else {
                return true;
            }
        }
        return false;
    }


    /*public static List<String> letterCombinations(String digits) {
        if(digits == null || digits.length() == 0) return new ArrayList<>();
        List<String> resultList = new ArrayList<>();
        StringBuilder str = new StringBuilder();
        Map<Integer, String> map = new HashMap<>();
        map.put(2, "abc");
        map.put(3, "def");
        map.put(4, "ghi");
        map.put(5, "jkl");
        map.put(6, "mno");
        map.put(7, "pqrs");
        map.put(8, "tuv");
        map.put(9, "wxyz");
        backTracking(resultList,map,str,digits,0);
        return resultList;
    }*/

    /*private static void backTracking(List<String> resultList, Map<Integer, String> map, StringBuilder str, String digits, int i) {
        if(i == digits.length()){
            resultList.add(str.toString());
            return;
        }
        int num = digits.charAt(i) - '0';
        String characters = map.get(num);
        for (int x = 0; x < characters.length(); x++) {
            str.append(characters.charAt(x));
            backTracking(resultList,map,str,digits,i + 1);
            str.deleteCharAt(str.length() - 1);
        }
    }*/

    /*public static List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> resultList = new ArrayList<>();
        LinkedList<Integer> list = new LinkedList<>();
        backTracking(resultList,list,k,n,1,0);
        return resultList;
    }

    private static void backTracking(List<List<Integer>> resultList, LinkedList<Integer> list, int k, int n, int i,int sum) {
        if(list != null && list.size() == k && sum == n){
            resultList.add(new ArrayList<>(list));
            return;
        }
        for(int j = i; j <= n - sum && j < 10; j++){
            list.add(j);
            backTracking(resultList,list,k,n,j+1,sum + j);
            list.removeLast();
        }
    }

    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> resultList = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                list.add(j);
                resultList.add(list);
            }
        }
        return resultList;
    }

    public static String reverseWords(String s) {
        int n = s.length();
        int temp = 0, j;
        StringBuffer stringBuffer = new StringBuffer();
        for (int i = 0; i < n; i++) {
            if(s.charAt(i) == ' '){
                j = i - 1;
                while(j >= temp){
                    stringBuffer.append(s.charAt(j--));
                }
                temp = i + 1;
                stringBuffer.append(' ');
            }
            if(i == n - 1){
                j = i;
                while(j >= temp){
                    stringBuffer.append(s.charAt(j--));
                }
            }
        }
        return stringBuffer.toString();
    }*/

    /*public static void moveZeroes(int[] nums) {
        int num = 0;
        for(int i = 0; i< nums.length; i++){
            if(nums[i]==0){
                num++;
            }else{
                nums[i-num] = nums[i];
            }
        }
        for(int i = nums.length - num; i < nums.length; i++){
            nums[i] = 0;
        }
    }*/

    /*public static int[] twoSum(int[] numbers, int target) {
        int left = 0, right = 1;
        int[] result = new int[2];
        while (left < numbers.length){
            if(numbers[left] + numbers[right] == target && left != right){
                result[0] = left + 1;
                result[1] = right + 1;
                break;
            }else if(numbers[left] + numbers[right] < target ){
                right++;
                if(right == numbers.length){
                    left = left + 1;
                    right = left + 1;
                }
            }else if(numbers[left] + numbers[right] > target){
                left = left + 1;
                right = left + 1;
            }
        }
        return result;
    }*/

    /*public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        int[] result = new int[2];
        while (left < right){
            if(numbers[left] + numbers[right] == target){
                result[0] = left + 1;
                result[1] = right + 1;
                break;
            }else if (numbers[left] + numbers[right] > target){
                right--;
            }else {
                left++;
            }
        }
        return result;
    }*/

    /*public static void rotate(int[] nums, int k) {
        int[] result = new int[nums.length];
        for (int i = 0,j = 0; i < nums.length&&j < nums.length;) {
            if(i <= nums.length - k && nums.length - k +i < nums.length){
                result[i++] = nums[nums.length - k -1 +i];
            }else {
                result[i++] = nums[j++];
            }
        }
        System.arraycopy(result, 0 , nums, 0, result.length);
    }*/
    /*public static void rotate(int[] nums, int k) {
        int length = nums.length;
        int[] result = new int[length];
        System.arraycopy(nums, length - k , result, 0, k);
        System.arraycopy(nums, 0 , result, k, length - k);
        System.arraycopy(result, 0 , nums, 0, length);
    }*/
    /*public static void rotate(int[] nums, int k) {
        int length = nums.length;
        k = k % length;
        for (int i = 0; i < length && i - k < 0; i++) {
            int temp = nums[length - k + i];
            for (int j = length - k + i; j > i; j--) {
                nums[j] = nums[j-1];
            }
            nums[i] = temp;
        }
    }*/

/*    public static void rotate(int[] nums, int k) {
        int length = nums.length;
        k = k % length;
        for (int i = 0; i < k ; i++) {
            int temp = nums [length - 1];
            for (int j = length + i -1; j >= 0; j--) {
                nums[j] = nums[j-1];
            }
            nums[0] = temp;
        }
    }*/

    public static void rotate(int[] nums, int k) {
        int length = nums.length;
        k = k % length;
        reserve(nums, 0, length);
        reserve(nums, 0, k);
        reserve(nums, k, length);
    }

    private static void reserve(int[] nums, int pos, int n) {
        int left = pos, right = n - 1;
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }

    public static void kmp(String str1, String str2) {
        int[] next = kmpNext(str2);
        System.out.println("部分匹配表：");
        System.out.println(Arrays.toString(next));

        int index = kmpSearch(str1, str2, next);
        if (index == -1) {
            System.out.println("未找到");
        } else {
            System.out.println("初始位置：" + index);
        }
    }

    /**
     * kmp匹配算法
     *
     * @param str1 原字符串
     * @param str2 子串
     * @param next 部分匹配表
     * @return 如果是-1，没有匹配到，匹配到返回第一个匹配的位置
     */
    public static int kmpSearch(String str1, String str2, int[] next) {

        //遍历
        for (int i = 0, j = 0; i < str1.length(); i++) {

            //需要处理 str1.charAt(i) ！= str2.charAt(j), 去调整j的大小
            //KMP算法核心点, 可以验证...
            while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j - 1];
            }
            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            if (j == str2.length()) {//找到了 // j = 3 i
                return i - j + 1;
            }
        }
        return -1;
    }

    /**
     * 获取字符串的部分匹配表
     *
     * @param dest
     * @return
     */
    public static int[] kmpNext(String dest) {
        //创建一个next 数组保存部分匹配值
        int[] next = new int[dest.length()];
        next[0] = 0; //如果字符串是长度为1 部分匹配值就是0
        for (int i = 1, j = 0; i < dest.length(); i++) {
            //当dest.charAt(i) != dest.charAt(j) ，我们需要从next[j-1]获取新的j
            //直到我们发现 有  dest.charAt(i) == dest.charAt(j)成立才退出
            //这时kmp算法的核心点
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j - 1];
            }
            //当dest.charAt(i) == dest.charAt(j) 满足时，部分匹配值就是+1
            if (dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }


    /*public static int strStr(String haystack, String needle) {
        if (haystack == null) {
            return 0;
        }
        if (needle == null) {
            return 0;
        }

        int m =haystack.length();
        int n = needle.length();

        for (int i = 0; i + n < m; i++) {
            boolean flag = true;
            for (int j = 0; j < n ; j++) {
                if(haystack.charAt(i+j) != needle.charAt(j)){
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;

    }*/
    /*public static int strStr(String haystack, String needle) {
        if (haystack == null) {
            return 0;
        }
        if (needle == null) {
            return 0;
        }

        int i, j = 0;
        for (i = 0; i < haystack.length(); i++) {
            for (j = 0; j < needle.length() && i < haystack.length(); j++) {
                if (haystack.charAt(i) == needle.charAt(j)) {
                    i++;
                } else {
                    break;
                }
            }
            if (j == needle.length()) {
                break;
            }
        }

        return j == needle.length() ? i-j : -1;
    }*/

    public static List<Integer> grayCode(int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < (1 << n); i++) {
            list.add(i ^ (i / 2));
        }
        return list;
    }

    public static void addGrayCode(int n, List<Integer> list) {
        if (n == 1) {
            list.add(0);
            list.add(1);
        }
        addGrayCode(n - 1, list);
    }
}
